This invention relates generally to systems for interconnecting processors, and more particularly, to a system which can be implemented in an integrated circuit for addressing, routing, and broadcasting information among a plurality of processors which are interconnected with each other in a hexagonal mesh multiprocessor arrangement.
The proliferation in recent years of powerful microprocessors and memory chips has resulted in considerable interest in the design and use of multiprocessor interconnection networks. Such networks are often required to connect thousands of homogeneously replicated processor-memory pairs, each of which is denominated a "processing node." In such systems, all synchronization and communication between processor nodes for program execution is often done via message passing. This is preferred over employment of a shared memory, as considerable difficulties would be encountered in the accessing of a memory system by a multiplicity of processors.
It is important that processing nodes in an interconnection network be homogeneous. This permits significant cost-performance benefits to be achieved, at least in part as a result of the inexpensive replication of multiprocessor components. Preferably, each processor node in the multiprocessor environment has fixed connectivity so that standard VLSI chips can be used. Moreover, the interconnection network should preferably contain a reasonably high degree of redundancy so that alternative routes can be made available to detour faulty processor nodes and links. More importantly, the interconnection network must facilitate efficient routing and broadcasting so as to achieve high performance in job executions.
A variety of multiprocessor interconnection systems have been proposed in the literature. However, most of them are not satisfactory, primarily as a result of their inability to provide satisfactory performance in all of the following: A satisfactory multiprocessor interconnection scheme should provide simplicity of interconnection, efficient message routing and broadcasting, a high degree of fault tolerance, and fine scalability, as measured in terms of the number of processor nodes necessary to increase the network's dimension by one. There is, therefore, a need for a multiprocessor interconnection scheme which performs satisfactorily in all of the foregoing areas of concern.
It is, therefore, an object of this invention to provide a system for interconnecting multiple processor nodes which is useful in real-time computing.
A still further object of this invention is to provide a simple and efficient system for message-broadcasting in a multiprocessor network.
An additional object of this invention is to provide a simple addressing scheme for a network of interconnected processor nodes, wherein such addresses can be utilized for computing message paths.
Yet another object of this invention is to provide a message routing scheme for a multiprocessor arrangement wherein message path computation is essentially insensitive to the size of the network.
A yet further object of this invention is to provide a message broadcasting scheme wherein the entire multi-processor interconnection network can be covered in relatively few steps.